#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>

using namespace std;

class Solution{
    public:
    //my ans --> time out
    vector<vector<int>> ans1(vector<int>& nums){
        int length = nums.size();
        vector<vector<int>> res;
        vector<vector<int>> out;
        if(length == 3){
            if(nums[0] + nums[1] + nums[2] == 0){
                out.push_back({nums[0], nums[1], nums[2]});
            }else{
                out.push_back({});
            }
            return out;
        }
        for(int i = 0; i != length-2; i++){
            for(int j = i+1; j != length-1; j++){
                for(int k = j+1; k != length; k++){
                    if(nums[i] + nums[j] + nums[k] == 0){
                        vector<int> temp = {nums[i], nums[j], nums[k]};
                        sort(temp.begin(), temp.end());
                        res.push_back(temp);
                    }
                }
            }
        }
        int len = res.size();
        if(len != 0){
            sort(res.begin(), res.end());
            out.push_back(res[0]);
            for(int i = 1; i != len; i++){
                if(res[i-1] != res[i]){
                    out.push_back(res[i]);
                }
            }
        }else{
            out.push_back({});
        }
        return out;
    }

    vector<vector<int>> ans2(vector<int>& nums){
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        for (int first = 0; first < n; ++first) {

            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; ++second) {

                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

void test1(){
    Solution s;
    vector<int> nums = {-1,0,1,2,-1,-4};
    // vector<vector<int>> ret = s.ans1(nums);
    vector<vector<int>> ret = s.ans2(nums);
    int c = ret.size();
    int r = ret[0].size();
    for(int i = 0; i != c; i++){
        for(int j = 0; j != r; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << endl;
    }
}

void test2(){
    Solution s;
    vector<int> nums = {0,1,1};
    // vector<vector<int>> ret = s.ans1(nums);
    vector<vector<int>> ret = s.ans2(nums);
    int c = ret.size();
    int r = ret[0].size();
    for(int i = 0; i != c; i++){
        for(int j = 0; j != r; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << endl;
    }
}

void test3(){
    Solution s;
    vector<int> nums = {0,0,0};
    // vector<vector<int>> ret = s.ans1(nums);
    vector<vector<int>> ret = s.ans2(nums);
    int c = ret.size();
    int r = ret[0].size();
    for(int i = 0; i != c; i++){
        for(int j = 0; j != r; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << endl;
    }
}

void test4(){
    Solution s;
    vector<int> nums = {1,2,-2,-1};
    // vector<vector<int>> ret = s.ans1(nums);
    vector<vector<int>> ret = s.ans2(nums);
    int c = ret.size();
    int r = ret[0].size();
    for(int i = 0; i != c; i++){
        for(int j = 0; j != r; j++){
            cout << ret[i][j] << " " << ends;
        }
        cout << endl;
    }
}

int main(void){
    test1();
    test2();
    test3();
    test4();

    return 0;
}